// https://www.lintcode.com/problem/number-of-ways-to-stay-in-the-same-place-after-some-steps-i/

public class Solution {
    /**
     * @param steps: steps you can move
     * @param arrLen: the length of the array
     * @return: Number of Ways to Stay in the Same Place After Some Steps
     */
    public int numWays(int steps, int arrLen) {
        // write your code here
        // DP: 第i步到位置j的方案可以根据之前状态推出
        // dp[i][j] = dp[i-1][j] +   ~ 不动
        //            dp[i-1][j+1] + ~ 向左
        //            dp[i-1][j-1]   ~ 向右
        int dist = Math.min(steps, arrLen); // 最远可以到位置
        int[][] dp = new int[steps + 1][]; // 第0步到第steps步
        for (int i = 0; i <= steps; ++i) {
            dp[i] = new int[dist];
            Arrays.fill(dp[i], 0);
        }
        dp[0][0] = 1;
        for (int step = 1; step <= steps; ++step) {
            for (int d = 0; d < dist; ++d) {
                if (d == 0) {
                    dp[step][d] += dp[step - 1][d];
                    if ((d + 1) < dist) {
                        dp[step][d] += dp[step - 1][d + 1]; // 可以向左一步回到0点
                    }
                } else if (d == (dist - 1)) {
                    dp[step][d] += dp[step - 1][d] + dp[step - 1][d - 1]; // 可以向右一步到终点
                } else {
                    dp[step][d] += dp[step - 1][d] + dp[step - 1][d + 1] + dp[step - 1][d - 1];
                }
            }
        }
        return dp[steps][0] % ((int)Math.pow(10, 9) + 7);
    }
}